package com.sali.BFS;

import java.util.*;

// 删除无效的括号
public class LeetCode_301 {

    public static void main(String[] args) {
        String s = "i))((()(n(())i((((";
        List<String> strings = removeInvalidParentheses(s);

        System.out.println(strings);
    }

    public static List<String> removeInvalidParentheses(String s) {
        List<String> res = new ArrayList<>();

        if (vaildJudge(s)) {
            res.add(s);
            return res;
        }

        HashSet<String> visited = new HashSet<>();

        Queue<String> myQue = new ArrayDeque<>();

        myQue.offer(s);

        boolean found = false;

        while (!myQue.isEmpty()) {
            int size = myQue.size();
            for (int i = 0; i < size; i++) {
                String curStr = myQue.poll();
                for (int j = 0; j < curStr.length(); j++) {
                    String newStr = curStr.substring(0, j) + curStr.substring(j + 1);
                    if (visited.contains(newStr)) {
                        continue;
                    }
                    myQue.offer(newStr);
                    visited.add(newStr);
                    if (!vaildJudge(newStr)) {
                        continue;
                    }
                    res.add(newStr);
                    found = true;
                }
            }
            if (found) {
                break;
            }
        }

        return res;

    }

    private static boolean vaildJudge(String str) {
        int leftNum = 0;

        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '(') {
                leftNum++;
            } else if (str.charAt(i) == ')') {
                leftNum--;
                if (leftNum < 0) {
                    return false;
                }
            }
        }
        return leftNum == 0;
    }

}
